package com.cmiot.gateway.luo;



/**
 * @author luowz
 * @version 1.0
 * @Description
 * @date 2020/7/23 15:44
 **/
class Solution0 {

    /**
     * 初始化1000000内所有素数
     */
    private static final int[] P = prime(1000000);
    public int splitArray(int[] nums) {
        int len = nums.length;
        int[][] arr = new int[len][];
        for (int i = 0; i < len; i++) {
            arr[i] = fac(nums[i]);
        }
        return len-1-content(arr,len-2,0);
    }
    public int content(int[][] arr,int n, int lastIndex){
        int end = arr.length - 1;
        int [] last = arr[lastIndex];
        if(gcdMatch(last,arr[end])){
            return n;
        }
        if(n==0){
            return -1;
        }
        int n0 = -1;
        n--;
        for (int i = lastIndex; i < end; i++) {
            if (gcdMatch(last,arr[i])) {
                int n1 = content(arr, n, i + 1);
                if(n1>n0){
                    n0 = n1;
                }
            }
        }
        return n0;
    }
    public int content0(int[][] arr,int n, int lastIndex){
        int [][] stack = new int[arr.length][];
        int end = arr.length - 1;
        int currentIndex = 0;
        stack[currentIndex] = new int[]{n,lastIndex};
        while (true){
            int[]param = stack[currentIndex--];
            n = param[0];
            lastIndex = param[1];
            int [] arr1 = arr[lastIndex];
            int n0 = -1;
            if(gcdMatch(arr1,arr[end])){
                n0 = n;
                //出栈
            }else if(n==0){
                n0 = -1;
                //出栈
            }else{
                n--;
                for (int i = lastIndex; i < end; i++) {
                    if (gcdMatch(arr1,arr[i])) {
                        stack[currentIndex++] = new int[]{n,i+1};
                        int n1 = content(arr, n, i + 1);
                        if(n1>n0){
                            n0 = n1;
                        }
                    }
                }
            }
        }
//        return 1;
    }
    public static boolean gcdMatch(int[] arr1,int[] arr2){
        int end1 = arr1[0];
        int end2 = arr2[0];
        for (int i = 1; i <= end1; i++) {
            int v1 = arr1[i];
            for (int j = 1; j <= end2; j++) {
                int v2 = arr2[j];
                if(v1<v2){
                    break;
                }
                if(v1==v2){
                    return true;
                }
            }
        }
        return false;
    }
    public static int [] fac(int n){
        int i = 1;
        int j = 0;
        int [] arr = new int[8];
        while (n>1){
            int v0 = P[j];
            if(v0*v0>n){
                arr[i++]=n;
                break;
            }
            boolean found = false;
            while (n%v0==0){
                n/=v0;
                found =true;
            }
            if(found){
                arr[i]=v0;
                i++;
            }
            j++;
        }
        arr[0] = i-1;
        return arr;
    }
    public static int[] prime(final int m){
        int[] p = new int[78498];
        p[0] = 2;
        int n = 1;
        int i =3;
        while (i<=m){
            int j = 0;
            boolean prime = true;
            while (true){
                int v0 = p[j];
                if(v0*v0>i){
                    break;
                }
                if(i%v0==0){
                    prime = false;
                    break;
                }
                j++;
            }
            if(prime){
                p[n++] = i;
            }
            i+=2;
        }
        return p;
    }


    public static void main(String[] args) {
        int[] nums = {5,7,15,8,14,30,13};
        System.out.println(new Solution0().splitArray(NUMS));
    }
    private static int[] parse(String str){
        String[]strs = str.split(",");
        int len = strs.length;
        int[] nums = new int[len];
        for (int i = 0; i < len; i++) {
            nums[i] = Integer.parseInt(strs[i]);
        }
        return nums;
    }
    private static String STR =  "847201,414313,28319,450257,340169,298583,354751,414209,219407,809803,301897,81649," +
            "499979,782183,909917,593,520699,676829,536953,79139,226199,516163,152197,167159,701023,341293,615233," +
            "351257,585733,181889,414109,32563,375899,24029,735659,188719,99241,360551,364607,931739,419789,838039," +
            "779131,406403,845129,625007,602971,591881,277499,717133,532633,13633,95233,12653,63079,69593,874193," +
            "1697,685199,540347,878833,445279,716981,516391,705737,647509,696083,803347,38903,677177,677309," +
            "276917,179143,434297,754891,887743,87991,396413,146777,28579,367541,411253,38677,359407,286591," +
            "293827,718841,160169,292301,465089,646897,937847,308311,873421,410621,52363,555209,199961,259643," +
            "455711,103979,564973,181457,711877,276239,897263,127643,447521,771899,217367,632363,533077,614167," +
            "524971,505111,703229,202639,20233,678451,899531,91099,849533,674537,700279,310129,295591,386329," +
            "37831,217069,578047,634523,744977,550801,853493,419687,739303,560893,72271,711539,840149,146369," +
            "530087,250301,709663,565651,347257,510589,195791,221797,795101,115831,80629,196681,737183,176629," +
            "243871,648709,206411,608029,117223,59419,938279,434977,353021,57679,63299,682247,842323,658057," +
            "293473,876017,724723,330287,689113,879859,428251,488249,675239,578131,439723,677791,766877,63419," +
            "918371,888163,399989,817933,132299,869399,903899,600293,491731,426583,347209,5923,456539,748877," +
            "944389,641833,288499,863803,416389,740561,35339,710621,495931,122579,401861,509293,880301,488749," +
            "585643,51341,98947,65851,629371,38603,231599,6091,477739,95773,158077,754903,632839,342257,916507," +
            "420613,535943,451301,1747,571903,558029,585953,693323,711173,82007,489673,75767,574657,506629," +
            "726191,598141,644129,467927,39163,141829,712357,437753,714037,252761,297881,72229,738721,908771," +
            "578779,722581,493939,859567,229,555383,720403,407249,466651,72313,794207,827857,825161,306389," +
            "494129,455977,783119,759709,5531,63103,65173,290201,231877,696349,771181,939203,442973,587137," +
            "694957,920519,243401,798101,727939,828127,34457,829267,534077,884201,32141,27043,682207,384331," +
            "144731,283403,682337,769207,709831,213949,914293,803207,109831,905207,920539,270899,218107,866713," +
            "618439,28573,626771,29077,504631,943477,504853,156707,485959,537679,217003,478483,195739,157999," +
            "159287,245389,155381,549097,25303,25303,185897,182467,672983,772229,341947,748387,354353,396031," +
            "330287,726379,646267,902017,241939,831653,402559,713191,711629,870577,860369,238099,693779,665069," +
            "471841,262807,174281,719569,297617,721793,90901,376183,103007,147503,203293,150533,449261,347587," +
            "709381,879839,232523,10151,162493,786061,485977,640907,165079,249677,190297,707767,758753,188261," +
            "538303,100129,392281,313153,569599,494269,239779,77621,624709,713827,900283,494933,736867,199819," +
            "178259,7873,525979,490241,555637,730783,46567,315467,536051,340129,617531,102797,232513,2141,828071," +
            "555857,419473,93971,723407,485207,1291,379679,867463,78649,554951,906839,689959,660449,47111,547499," +
            "620239,937253,672377,488959,488959,549713,861647,582689,357619,166297,16183,430979,162611,592741," +
            "777181,61981,181213,56167,758713,821329,308051,635809,189151,587579,172009,311137,44071,722027," +
            "689107,525433,763237,153941,596569,63361,197,932117,356479,193469,410519,384481,825527,38239,697271," +
            "545773,34687,979277,607151,600889,576049,629927,633091,921463,64793,11119,385661,805271,661897," +
            "825049,269953,101119,845017,200401,58169,523177,944417,377387,319511,159787,823241,414083,82141," +
            "885427,580673,26141,575591,940223,508091,381739,100673,68023,215273,910939,453461,541987,573161," +
            "762211,485209,729821,629177,228799,909089,132689,867233,248753,417863,209159,37967,72661,222791," +
            "652241,795329,53831,527453,719833,545141,32117,567487,297161,392209,560093,836233,299653,633001," +
            "811259,353149,6247,203563,343639,174491,103457,845941,923971,344167,770281,132283,747731,339341," +
            "438671,105533,353,840149,577667,391301,531331,139067,102251,858373,72859,497701,70297,131611,136979," +
            "616997,465679,705389,946919,351497,553681,752903,58439,169843,177223,245473,186583,912991,347987," +
            "927167,104891,379333,525949,458317,189583,733687,491167,775741,271451,405143,773117,208997,821551," +
            "95441,353819,893161,170239,174263,791081,447439,513031,800573,207953,762583,732187,446951,507713," +
            "208493,614321,425317,651689,315739,129187,768041,384367,891563,6053,104231,76673,78179,361337," +
            "198413,668821,190717,524119,605993,96763,695089,341983,687331,313969,872453,616961,692651,41761," +
            "191297,458053,588167,726457,803417,123269,233327,172507,392599,373151,595373,755707,337903,739637," +
            "546587,115873,495953,612107,421037,651811,702469,918443,52253,869777,802471,104087,694277,614759," +
            "786887,134191,887693,872657,122789,886189,581293,553369,321443,452393,880367,403327,529933,836137," +
            "581551,377537,819253,580919,805339,404851,57713,776357,151799,292837,28661,281623,357503,314879," +
            "401773,119963,65381,440939,456409,343639,135649,352493,501967,389849,228953,527851,926489,684557," +
            "561761,450209,618593,19571,627041,850417,58711,668671,807119,266933,608519,442831,60223,53699," +
            "265541,950401,857471,462739,921463,434501,88747,626581,918539,62581,276337,42649,750137,177467," +
            "277597,739051,319001,835001,344269,73141,827347,581263,143977,889363,858103,804007,372707,546283," +
            "725119,300967,139981,383659,221813,285721,646271,27367,619373,395849,518597,191473,524287,889429," +
            "258403,423091,774811,76333,638171,458039,713347,573317,197803,584561,95483,722563,334333,44089," +
            "823169,252157,280729,433201,553643,11909,305633,311203,627947,225263,160073,695999,821099,99371," +
            "616849,619363,614717,425779,131939,261013,749083,321007,172657,309167,408263,471901,770527,914941," +
            "487651,305719,124459,252457,360851,846353,781453,185821,204299,604699,386651,148669,223243,703229," +
            "935183,759329,382373,802721,27479,633667,346439,592853,905269,908549,612331,765587,946987,73379," +
            "315691,777863,591301,617819,589163,800573,468371,240263,780931,746533,786937,760993,71741,912859," +
            "580939,676829,80789,875647,620567,691343,98123,234007,733333,766807,202889,634471,822299,80077," +
            "769999,795467,561419,816203,618119,13967,548579,525127,814531,393247,881269,841411,120661,622399," +
            "56633,89137,18617,170029,687341,24977,618589,325999,187559,452953,552283,676493,890437,941209," +
            "589507,913139,337859,652549,334603,356929,425713,179671,165083,870871,35677,581947,78427,297509," +
            "872479,220351,287933,585271,354353,95731,559633,756323,245389,458987,115061,780343,169307,54833," +
            "534049,60539,307019,390539,496477,494671,825991,741061,37199,329999,60373,864137,74419,153611," +
            "798097,122557,525001,364853,225353,487073,574003,547769,851603,8017,675739,268999,813971,164321," +
            "153449,71867,112249,743123,209929,597523,776921,644053,104003,413557,129169,438517,138661,139409," +
            "721307,539863,199457,737753,538877,401861,544451,31469,643051,73277,806129,674759,816559,390889," +
            "702887,845203,233921,228793,798757,147937,103099,464309,208927,704551,367181,451277,295319,583537," +
            "432781,12049,670487,831587,166151,233617,488153,601231,660643,37379,302299,325231,930571,441043," +
            "200293,802297,936659,296971,526381,610217,878869,425107,279317,931543,713807,483577,794531,397751," +
            "740521,311419,100297,379993,436097,132469,168089,644353,589291,648563,925921,698669,427327,212633," +
            "939599,141073,55439,423779,492281,74257,248243,313549,511013,453161,898279,150383,932431,189949," +
            "599551,422923,912413,718937,404539,914359,647821,421501,750553,688573,836677,585461,590357,835733," +
            "619331,722983,626251,345643,42557,167777,617917,597269,704303,726611,507301,5563,326701,281297," +
            "878039,798823,255467,534697,372719,722077,55633,714887,6571,596461,448883,110923,483409,429449," +
            "370919,166861,283447,49831,6971,630181,95723,181967,273821,579083,295777,150077,613993,774427," +
            "375251,251059,565867,852149,426301,242059,668821,205397,797003,891101,853739,34841,100613,392767," +
            "808369,417317,45083,607261,245171,846067,368609,592307,359633,118583,569419,924151,859273,114797," +
            "278581,79817,915143,189479,261427,286813,523463,155699,473953,315349,323207,65543,688223,26423," +
            "59443,218077,305047,97711,233747,135301,394019,168533,173747,278591,104959,98389,835841,446387," +
            "275489,894973,682411,645019,886493,949979,427969,536293,571939,820733,124643,40841,801103,528413," +
            "17569,31183,676649,463031,367573,526997,214021,510817,66137,875593,694763,696523,254021,128291," +
            "857539,338033,935303,754279,690839,384107,281959,74887,798179,72271,894167,290539,487727,369079," +
            "32369,88169,197077,924191,704303,898787,376199,96737,868459,331819,844369,30697,503791,773057," +
            "316507,425783,228233,877867,933047,837721,946367,479639,194413,914327,268207,12659,837059,746233," +
            "816341,426319,762373,790817,909379,494693,20333,777041,461009,747391,704287,877699,87973,835831," +
            "916103,655847,726611,587123,848893,755077,779413,929609,79397,170857,621721,412033,23789,768653," +
            "485657,395189,93229,225023,898153,20359,818977,256211,72817,301471,595709,11243,660013,91921,836191," +
            "535999,218111,626987,425641,32359,297151,706561,319289,468683,736823,697181,282241,845231,154291," +
            "345487,927847,401119,727877,566911,477277,771011,324587,609173,81973,5147,408719,239081,931757," +
            "792973,567829,137743,932081,882389,202949,23269,642853,893131,908419,408049,736027,356981,548909," +
            "879539,277427,150401,363059,710261,688393,47857,401671,340339,542027,565973,506729,212801,853793," +
            "362393,948457,775613,257731,560621,348269,490223,597757,700237,531833,929623,874847,942143,736639," +
            "677147,877313,455527,917849,154211,220019,7523,503869,691289,808361,492007,58441,311407,75079," +
            "561923,462437,540173,65647,109673,916907,11971,21751,68443,530983,934579,110651,164893,149057," +
            "242863,509023,727691,225257,274711,724187,501593,807707,211349,834523,335123,146239,27487,680417," +
            "21247,839351,157273,657313,394759,885823,738863,521009,111253,578971,252829,154157,232681,144889," +
            "628207,444293,36683,927097,872659,941263,829537,565163,117809,39863,298601,848707,542551,900869," +
            "15199,38377,643301,422911,895159,735421,518809,535061,197831,757753,676421,55291,259781,498209," +
            "422203,360293,731719,688799,722147,648671,11131,197441,285497,800497,761869,729821,620467,880097," +
            "90787,479147,748823,457043,650927,785641,593111,141181,285433,306011,95369,546149,723493,424091," +
            "336353,104593,727261,551543,253447,10321,588641,933677,473419,249833,901819,12647,491651,886247," +
            "823201,41627,781967,148429,649499,578047,753677,13763,49277,874543,869437,888061,575791,782497," +
            "260003,233923,895507,855851,505283,553507,90901,686911,947579,786697,942541,95629,465821,9323," +
            "764539,204007,42821,225223,944077,126079,13103,880199,67651,809569,227603,113177,780697,944777," +
            "139787,447463,521317,261439,723491,76673,315803,35447,241067,106319,144737,539309,576469,918361," +
            "212881,821,365137,632503,866857,428977,16661,837461,431377,544543,280681,752137,27109,296347,905137," +
            "105199,3307,587219,55901,203141,373207,699299,763369,13441,152029,343901,602309,497117,862441," +
            "249517,84653,855203,650971,14779,358213,744397,350423,310397,542131,2579,169471,179,336253,585601," +
            "11743,90011,716743,442031,587441,850943,463613,1607,91463,583619,567871,82609,872017,339557,689879," +
            "128819,850121,827927,71437,825749,35969,4567,151507,927833,530249,102911,46219,49169,676349,391397," +
            "898607,332641,907549,634853,675823,210233,689081,863,870413,927653,250703,486971,301703,132929," +
            "749153,156727,95869,222953,352757,662671,589241,493657,586457,339091,716459,409823,231503,442439," +
            "21313,290663,605947,876607,566557,242797,716981,263267,913417,270311,578621,273253,369293,759457," +
            "597419,398393,344207,322339,576431,112859,89413,548363,421739,882593,718381,456949,7151,413827," +
            "336221,253811,218419,208493,649801,101267,700223,612583,768811,733433,948287,913873,797869,365423," +
            "123667,136421,679067,935359,909803,583031,394357,751001,546587,450227,381911,126961,611839,42773," +
            "14537,194017,9133,354307,699817,15541,194749,508159,164477,200443,53407,189713,847657,296797,489833," +
            "234067,21613,497989,169243,770417,344209,219143,932131,290347,354037,191119,114083,596341,715801," +
            "524197,856487,572581,219761,651331,493277,770839,61043,235811,802661,578131,811919,442987,342679," +
            "114467,97577,680353,40637,43781,187189,233297,36931,65617,339161,849973,457607,745307,851801,357169," +
            "329717,149309,47293,638717,694357,844601,96329,418721,813157,396299,88261,831043,620251,601231," +
            "79987,835319,33857,354073,922283,132529,590171,832483,660659,370483,624119,119627,515651,50581," +
            "714551,120977,429449,288907,18061,717797,529471,259631,371843,304259,23743,468913,794831,229819," +
            "461009,55903,21191,170749,149021,662339,377071,272863,747839,578309,818291,543671,413167,498859," +
            "404197,250739,501019,636421,689963,888653,314927,84659,45413,37097,810443,464213,893029,584057," +
            "39047,352909,817147,790099,115061,697523,589139,126541,618637,328127,865681,817793,168227,265129," +
            "817319,86311,874127,137077,849391,513013,301349,415993,64553,728131,884857,299539,109331,20359," +
            "870341,27953,456821,99041,594037,823663,493693,672949,576551,665447,833843,679793,83399,700363," +
            "765293,32869,358601,568189,191141,562301,108739,599561,699197,609373,245909,950281,650599,204623," +
            "205237,838781,646909,712601,462713,935537,286103,126211,657049,117911,96527,557831,204583,29921," +
            "814063,452549,896299,336929,718457,398621,765881,928427,115769,109133,502277,608339,676961,368803," +
            "704857,142211,202289,421913,187651,771389,370009,40883,501401,576967,702743,756727,747283,9719," +
            "452857,677563,182953,355007,250583,569269,360289,332489,880799,323009,40927,765533,10987,647441," +
            "107273,438937,350563,912467,529183,837077,923407,909863,148727,125201,147919,722243,570637,146543," +
            "281839,116491,251177,800083,739601,554503,948799,864221,577529,18859,302629,418073,19427,827041," +
            "825533,553043,443749,302999,255523,39241,56003,745477,102013,325543,662843,250837,588743,164413," +
            "723109,728281,477947,375049,785579,462499,553463,522383,622151,203989,807907,503317,683693,319279," +
            "67,141359,188953,139747,491851,517747,788317,607933,481769,44983,234463,352411,159911,860969,175573," +
            "19471,714943,401053,110251,108631,34843,712021,87133,827231,604069,27739,700171,115183,229703,45821," +
            "865103,215183,93229,93719,431831,481699,140557,279949,180419,614717,172213,158597,349007,729943," +
            "544937,234499,84407,164531,533003,54269,219169,632627,928351,522523,894917,817183,183299,543853," +
            "157231,541381,891389,600203,759571,266003,206123,318917,762499,739021,171803,603013,451937,786061," +
            "277993,628189,152267,44273,661103,222107,219647,896521,659783,768643,890161,223273,885733,86413," +
            "353459,419933,470087,558457,469237,328931,914887,644117,90901,640499,267479,386047,884423,46441," +
            "247691,686051,550369,735953,927841,148891,941201,32603,8779,520031,815413,773249,462727,33587," +
            "604313,629491,919337,908597,154667,187091,214531,56659,689131,108139,895291,464137,523969,824977," +
            "689107,330287,937927,552193,921197,232741,23173,213263,278233,539743,696763,27437,296587,14533,4943," +
            "120833,29101,783487,360007,352357,259717,729719,91939,459763,456329,506339,885991,73363,934001," +
            "427423,254941,177433,452497,829883,233371,805279,1279,13913,516679,281423,307529,899189,221401," +
            "67157,734221,455933,557927,336181,911371,275491,874567,502081,193619,940703,571147,213019,268547," +
            "320141,18229,280339,377963,829057,281839,183697,173867,236293,620251,529127,48197,191717,813767," +
            "462569,625253,832913,318889,177913,218069,892627,224327,685337,114679,469877,550427,182641,264403," +
            "706337,598571,584981,630107,109789,7477,804449,178481,771961,926843,864947,479881,112247,179909," +
            "777221,87553,464809,270269,102929,772379,423209,418751,709417,195029,163661,531857,901993,128461," +
            "102643,498599,229727,250969,878789,433373,949391,175993,50849,377789,318641,878929,922021,844631," +
            "875341,323093,697157,284689,161869,312779,526117,795763,413911,349729,160409,180497,297967,3187," +
            "492587,161591,144203,724219,5227,423413,648239,950231,660559,680489,714377,232459,292471,179737," +
            "285031,41011,862177,741883,801461,925597,189253,701629,14549,738623,726071,480517,738457,600071," +
            "367649,57223,874303,930011,740711,137219,269461,883639,675131,92399,834013,769429,173,178469,585019," +
            "403661,514571,320659,303013,746797,49367,389447,642079,652507,706309,25463,456791,466579,235289," +
            "880303,836821,556987,616741,604477,362353,345601,5471,723157,868559,727049,355643,579893,204437," +
            "188857,478897,93971,147457,129707,864221,911507,868999,630863,152519,639757,618509,635263,942779," +
            "141023,316703,937969,147607,810443,225611,536059,210671,35117,716809,558197,2143,330047,65677," +
            "198647,798799,873263,721219,640193,431029,736093,788999,208189,44777,800473,309289,497153,794741," +
            "874387,899189,385289,521693,868691,484447,738349,743143,714601,554419,413827,283607,152777,73121," +
            "840319,820763,761161,18013,776221,732257,62989,882599,48821,637271,673529,684637,524413,540877," +
            "738121,824179,67043,452329,60727,454513,754027,798143,707459,39827,31973,740371,536933,305449," +
            "132109,456517,708703,425813,23767,435731,171707,639851,147097,127033,772003,292759,383029,205483," +
            "80347,571903,10163,521603,610651,321143,572843,536749,42379,889309,133213,602639,215927,746563," +
            "574081,934693,661091,390101,166723,815197,499183,138797,317539,128659,50513,161807,704243,575699," +
            "759287,390527,802463,519551,360949,201511,839203,474959,384697,858707,671633,593051,274019,781817," +
            "153277,159839,67867,162937,358951,41659,105023,915539,508259,656791,489959,218923,355529,818231," +
            "696569,197269,657311,424997,298477,332467,130199,529987,922123,425473,930773,212999,855727,56767," +
            "727997,347227,828953,769619,464143,67559,346417,374903,495557,356761,906847,215899,518867,38803," +
            "103349,933553,286789,558083,905651,835607,346393,158597,651397,562721,949973,123059,230303,127663," +
            "395581,103981,917629,437473,122741,582821,921913,163433,796801,30187,773081,283721,90523,63863," +
            "17393,270329,255989,666091,246469,156887,458963,412739,507113,147769,203953,100559,288049,335507," +
            "647771,404843,463483,606997,997,571969,735871,895087,198281,787243,224669,85037,232597,288853," +
            "425233,128153,830719,580331,192043,443363,510529,143971,575791,554303,310087,866293,443939,459293," +
            "397687,443587,137743,691153,56239,86297,466181,214651,81563,44687,5839,120551,70843,678949,318679," +
            "509723,395873,384359,505313,727249,557533,609907,289019,253871,51203,16519,453949,323803,392467," +
            "24061,719183,142327,940003,390809,929311,797851,709823,508373,894211,42281,585749,294991,434111," +
            "562699,518447,814081,184271,448141,323251,728971,835271,834439,867059,109049,789419,374681,937813," +
            "56359,690059,154183,918683,792151,832331,801709,243911,692467,19219,385013,704747,36389,774803," +
            "434011,112397,29803,51473,357859,851351,119551,608497,946549,22397,870811,921959,30661,923179,60449," +
            "197063,122011,222361,90059,703139,495637,251887,107857,147937,324097,226103,765781,793789,285497," +
            "20719,280229,668713,777143,752503,13259,806317,115523,350089,873781,700573,355499,837937,279311," +
            "271241,248987,5471,492403,349931,411013,576131,679519,295847,171881,789671,918259,584677,519107," +
            "510817,228127,376399,179581,65699,322573,120847,492551,464993,98737,324131,20389,391879,518239," +
            "947033,11789,850229,788687,523357,779347,306023,47951,113947,943783,698413,56113,143729,148243," +
            "281327,224527,164449,697973,803731,936941,531589,127133,799837,214789,895903,325487,713159,801403," +
            "764327,202757,888091,536869,56209,213349,589681,676703,692707,295037,434933,877043,568619,284311," +
            "306169,438259,655267,138967,50287,199181,768437,872129,889877,89519,477229,582181,24247,91291," +
            "380047,350459,409943,832963,283411,349759,137413,461009,51061,918793,787777,160387,613861,715577," +
            "591443,672227,317021,843559,946507,784249,488573,559991,175349,245087,480761,843443,132421,678641," +
            "582821,120017,580691,44641,336151,687131,741001,731803,220931,392233,881191,361507,185813,423847," +
            "794693,913027,538709,466303,674189,666403,102367,615767,863879,131171,451411,314513,542933,690553," +
            "568289,265117,743711,101281,807647,765581,101513,414679,189743,617131,239539,502829,186581,352867," +
            "947407,547369,122743,3203,87037,99223,781229,288199,798521,595093,686141,773863,749167,182473," +
            "365903,191447,393017,228953,640529,511223,876731,393077,919169,7789,320339,709967,572639,763267," +
            "813419,250423,76829,216577,95239,131251,751151,349079,200869,120563,667019,78283,697691,844483," +
            "834761,616769,357083,279511,862289,779981,471817,52543,709981,322999,699401,245299,549281,420677," +
            "653641,759617,646543,735781,644863,34519,578353,885737,396449,507907,914951,736961,66791,727169," +
            "851419,861239,26119,483709,185303,230597,225347,912049,923203,713653,252193,138181,698779,898291," +
            "921293,87277,3433,601037,553529,182687,17623,356591,833669,253751,172583,140909,812599,192613," +
            "947753,741061,367121,133013,514939,614729,688087,184039,468737,813157,911327,835687,14153,678179," +
            "162391,597929,722363,395887,760759,605873,880961,278981,896561,559967,3727,555523,482689,337817," +
            "512009,383107,721613,390421,787811,73583,752519,216481,751301,306877,31327,390961,827143,167021," +
            "944929,252223,880871,611111,683737,802331,197597,677357,394363,210347,737999,886469,94261,238103," +
            "521429,20983,6199,778633,351217,217859,689341,320039,545497,499679,528091,633823,99487,578537," +
            "808991,731611,930911,799859,551063,907199,300721,900019,99877,809797,34757,6841,509959,341443," +
            "577901,105239,282299,600217,800873,437861,76771,86423,295769,5147,579829,649651,661513,45247,184651," +
            "172069,676037,76991,243863,947627,586819,857459,742723,366001,101159,471929,530843,305821,386249," +
            "307919,243031,925849,192617,215771,402383,873641,89977,190607,376471,600269,102667,941747,824911," +
            "700229,546137,865511,896719,244567,133073,745697,55823,517861,350617,20963,398149,328063,177043,443," +
            "243839,722369,62603,495199,622621,228617,429043,797557,702743,164653,693683,327443,608953,172421," +
            "247393,505447,546047,30389,602111,777817,692017,430121,849829,255371,271517,709451,790817,43913," +
            "273979,556573,172801,630247,6701,194521,759149,438707,415343,528403,691973,922561,381011,749891," +
            "506357,663149,861293,665843,364621,662797,55661,609997,851131,81013,468683,301051,945589,17977," +
            "224947,821333,811081,763369,324517,455159,598049,17203,893863,676763,140363,806317,582371,673109," +
            "629537,873079,398903,482717,532001,56113,4157,392761,710491,827851,125813,853733,894611,404419," +
            "892603,2099,109849,556181,277169,394393,73757,847937,631259,325571,78623,388693,225977,463219," +
            "356821,154543,324097,614759,889177,32341,163789,198823,293773,770459,634157,399031,730157,341951," +
            "122027,301759,864509,197101,944429,773569,781351,544123,646669,8951,695477,476743,825073,171007," +
            "703561,308149,160723,297719,945767,179167,838613,578827,481147,240341,371141,681763,335507,316439," +
            "659689,255869,267959,670541,12473,760183,131231,481589,258241,460073,174959,153641,727589,18553," +
            "179209,491719,870271,740351,678133,268823,253909,398441,493919,278233,291983,392087,432721,258803," +
            "717683,212369,638327,375341,358859,514343,380623,224069,3673,145193,655597,132491,430019,240967," +
            "710389,612217,581947,736091,798059,737327,392033,624839,33119,136691,477131,333269,891017,455989," +
            "409099,47129,783677,747239,617677,136649,598877,575551,530209,668741,234833,861857,253387,605597," +
            "706417,385331,178873,288317,271969,945701,824983,260017,676601,27103,40697,800971,268091,580033," +
            "76387,127669,815411,11927,393383,213263,757403,874427,601231,419777,464819,870031,321947,692789," +
            "238093,733427,825701,192743,280817,169111,657383,652207,38791,429917,364571,317701,835441,524413," +
            "145109,289249,346903,206077,578131,204623,937693,546367,284413,328043,590833,942521,552031,600283," +
            "762409,277007,310169,40433,18713,324781,927517,401887,416389,143527,678719,306857,827501,124721," +
            "870461,670447,400441,3121,621419,324319,515371,386339,541129,363683,665773,116351,418667,531331," +
            "161729,695899,172541,639361,588097,77471,428807,518083,120749,551059,133187,5903,828731,668579," +
            "834469,2237,546071,789623,65927,616129,61261,166603,8887,823457,391639,125669,672823,849103,787091," +
            "139891,765659,432359,768259,126613,560299,81839,924811,288653,484987,490631,754993,931129,702439," +
            "412273,683819,71867,187303,85427,644977,619831,219143,344821,741229,489959,465781,9371,438443,84191," +
            "912649,330907,384913,508961,4261,32771,567499,271217,847051,680161,424163,17359,532241,245563," +
            "923833,558241,202661,929843,74357,233069,787277,685019,476089,585619,702913,514747,236399,517169," +
            "589711,44249,585883,368359,603023,28289,163633,510889,607939,607129,386279,850177,17077,254803," +
            "260569,124601,53927,868999,473471,49277,803609,496841,515761,470579,655289,84719,366193,32909," +
            "787337,341597,8837,281023,391199,816887,500923,556181,842353,737159,66067,69877,627961,545387," +
            "939551,60497,839903,428731,100459,947501,186007,446863,669857,680081,541711,17021,386839,255649," +
            "840289,6551,131947,302801,164513,157351,359389,556343,272267,580477,657017,718657,288839,539129," +
            "881077,444937,190339,894893,27751,855511,26687,236053,458639,50051,822691,102241,101221,939931," +
            "632993,71917,595267,131839,379997,211723,145207,733477,359713,617731,695281,104527,58453,686057," +
            "713411,948391,418031,237733,776561,160309,719989,876433,470621,436811,586811,905647,102019,362903," +
            "68767,672629,467867,760997,77383,85577,865231,462901,97673,364921,821333,891559,576431,577427," +
            "119557,208037,47123,622159,543223,2087,660199,701329,928159,470227,792109,752527,121967,886339," +
            "862501,858101,542299,896531,268343,691979,771481,192383,300589,607331,520547,403549,296557,111271," +
            "57697,159017,848321,571589,745243,608899,704027,413753,150827,121631,80681,74923,800089,111427," +
            "583469,415759,343381,179461,225583,462697,309559,579017,355087,374029,200797,610031,426287,875129," +
            "407203,228913,344753,106661,338161,939413,230683,233069,659621,256939,849923,810881,389999,752111," +
            "696853,619813,88469,700229,323927,636241,488161,822683,925103,788071,934039,483317,811753,459619," +
            "264757,66749,195443,228757,182261,678413,800159,113761,653579,7069,739121,682733,718633,330149," +
            "321817,262901,392699,557371,344893,171673,121909,605443,251527,843299,142067,160907,160169,109313," +
            "733639,392087,848849,740581,42943,929059,31063,52189,341447,928111,255511,512713,720367,633079," +
            "576523,540863,944591,628937,768461,390263,232487,21599,371797,834023,844769,746843,27961,367531," +
            "620731,217771,612041,170081,261739,576727,504799,377129,376823,303619,749557,142357,897077,39239," +
            "375667,12323,635849,701177,431533,645581,864757,777619,15991,207797,524081,843763,229753,581333," +
            "466649,467729,279029,377219,843079,109807,580759,144961,799489,526213,40627,207709,680531,507839," +
            "7331,137,541181,802177,252691,390323,911737,89431,698021,272351,301219,739031,593479,194179,791017," +
            "918041,749143,628811,739283,780917,615401,923869,377291,384437,865801,430487,261977,583351,173629," +
            "520549,497449,340381,457789,138373,330019,92363,189067,313,915221,803057,152947,648079,85639,201011," +
            "581981,475151,571531,27851,676961,651019,318781,24251,822973,267763,915947,893449,690583,719713," +
            "826669,121697,508771,602111,335341,50441,832999,384287,318863,802979,289213,383417,632483,209029," +
            "698017,649073,176317,793297,53377,679223,785203,879653,156733,266401,875513,261619,713681,172517," +
            "33937,482483,446279,554833,505321,599657,248789,697523,506591,303749,223243,781889,663979,837467," +
            "210131,406661,598649,163003,136963,670097,778301,102503,418603,850373,778537,785809,393137,396983," +
            "804703,906461,680161,750163,353869,545791,195997,744113,720767,90353,601507,731681,814543,744301," +
            "716389,175897,842003,235369,691921,1019,713417,24623,442121,254213,157327,844483,764809,770873," +
            "843091,759433,273979,592351,569141,709469,350003,823399,451987,840703,915253,706631,530693,900461," +
            "300719,554707,33091,690793,458407,131251,497597,45893,321007,422393,286513,924967,803611,460297," +
            "604349,532187,847673,572423,84691,288823,781897,454229,343897,219851,210967,620239,892159,368171," +
            "116539,50891,453961,819157,408689,667321,418751,331663,332117,936599,816209,850433,531203,723907," +
            "538331,611111,89867,554803,1787,11317,814717,415447,198439,574493,316321,772403,830257,447893," +
            "825389,349907,176557,873083,437287,715727,84211,152407,71147,11411,476419,617843,818887,821053," +
            "161527,131317,526943,42899,378869,570683,760141,717533,280883,891889,92479,280537,270841,247391," +
            "185183,20183,141863,361373,295843,144163,814991,754121,788959,545917,15451,59467,15641,30911,749453," +
            "459031,704681,928079,749257,880427,65777,550811,136897,523493,171917,464539,660683,456763,500107," +
            "351383,187927,924019,641813,559051,845179,657779,626833,892471,627859,845683,806549,178151,561461," +
            "801337,130379,412051,417097,213407,652573,588871,147137,76541,118033,169493,935677,75659,754183," +
            "172741,307823,95191,662537,221159,172399,254021,566821,143807,922081,771437,916939,63667,851899," +
            "627433,384227,742307,413033,780343,372653,683597,327319,474337,574477,538297,17203,617107,144589," +
            "35573,291107,78691,113537,741101,807797,907163,769799,673837,340369,610829,506743,80681,65101," +
            "360949,219749,833299,474907,666091,812587,548347,74311,746957,602627,852989,338839,363809,142111," +
            "215353,639487,806257,201337,436279,654221,739579,194093,78031,806297,566977,566443,890119,32479," +
            "298477,665843,166399,61561,619397,891001,301943,722317,399871,253993,915917,291509,440509,438467," +
            "100411,603989,897473,745757,493001,11971,774803,424849,562901,911413,268171,265037,177589,699863," +
            "434039,73517,557159,867547,468137,926633,77069,572497,367781,413299,837737,850453,460951,653879," +
            "197077,377711,648133,85331,853759,482641,464143,225503,197279,917803,314813,313889,683041,268403," +
            "337343,700597,161167,441587,534301,612971,700057,82217,255179,444007,738643,430883,604529,209381," +
            "507937,127403,219251,464173,443129,57287,468697,97379,422243,458879,87037,648677,656939,252419," +
            "556601,806017,318691,37663,428003,375341,872203,481171,210643,705127,373,420677,64781,892049,611603," +
            "44483,161071,762101,110533,560123,496849,438281,130981,161387,377653,582563,891563,816251,307823," +
            "438047,878629,865327,332509,210907,253081,479023,332641,142553,280729,273979,773869,701023,615623," +
            "206281,93133,583279,321371,303529,266477,457057,816451,408773,460181,652343,470471,278819,537157," +
            "580631,242093,498367,112757,624259,846577,62897,361927,823993,66721,115837,263513,704579,144167," +
            "244403,305717,398491,905507,337861,88241,215681,34313,379979,937337,429497,253439,478403,337529," +
            "181814,108131,721117,660227,359311,122869,521357,83701,127781,97859,654923,399107,354971,488171," +
            "530447,235787,886969,261347,628787,766559,641867,809297,599353,437093,445229,314569,348077,234361," +
            "706049,10691,53117,491423,489551,383777,765203,37223,123479,524347,642113,367613,193603,769807," +
            "356761,284657,450287,388903,49627,420557,86861,357817,695243,540907,3079,580291,9049,825389,72383," +
            "549449,844601,723043,911077,831253,328051,191561,732827,921203,808523,195761,237271,936527,426779," +
            "670363,706481,29333,287887,90121,424129,824077,746363,299743,832607,168673,216173,95461,347057," +
            "399221,404249,737531,632371,347993,85703,74779,141767,782941,396437,449653,14461,408809,541231," +
            "552283,576727,257687,54499,330167,818887,185323,63671,374089,206641,151607,118457,615493,831091," +
            "602461,43063,136993,248987,777391,395113,810389,566617,144139,9679,667999,247391,848909,434803," +
            "298477,732731,55871,330641,842969,747259,1753,577427,756043,91453,614659,896047,63199,757811,744137," +
            "923407,472793,761161,710959,846721,83869,618869,353173,402587,278849,871987,196853,349927,757879," +
            "945577,566879,253949,358973,651437,855521,418927,477977,704867,766867,166741,435881,704017,40849," +
            "192611,194671,754577,566231,207517,658051,301669,280409,169259,623669,414389,278459,53831,127781," +
            "62131,763621,59539,680879,216157,288461,490339,705643,30841,121039,690037,544277,696889,856547," +
            "270899,533053,529393,11941,774083,185123,11681,948593,644863,114649,354373,719419,626239,757247," +
            "538301,923249,298307,591161,210139,430891,553981,606443,880573,56873,500947,711539,872387,78467," +
            "699697,187877,325379,428671,8273,699379,78593,164209,854929,476519,133379,355517,693619,833363," +
            "946177,720877,380059,763417,268189,525491,157307,914657,876817,365147,373567,290429,166183,94379," ;

    private static final int[] NUMS = parse(STR);
}
